package combinationsum39

func CombinationSum(candidates []int, target int) [][]int {
	result := [][]int{}
	combination := []int{}
	backtrack(candidates, target, 0, combination, &result)
	return result
}

// backtrack is a helper function that performs the backtracking algorithm.
// It tries to build combinations of numbers that sum up to the target value n.
// It takes the current combination, the starting number, and the result slice as arguments.
// @param candidates: The list of candidate numbers.
// @param target: The target sum.
// @param start: The starting index for the current combination.
// @param combination: The current combination being built.
// @param result: The slice to store the valid combinations.
// @return: None
func backtrack(candidates []int, target int, start int, combination []int, result *[][]int) {
	if target == 0 {
		// If the combination has k elements and the sum is 0, add it to the result.
		combinationCopy := make([]int, len(combination))
		copy(combinationCopy, combination)
		*result = append(*result, combinationCopy) // if code reach here, it means we find a valid result item.
		return
	}

	for i := start; i < len(candidates); i++ {
		if target < candidates[i] {
			// If the remaining sum is less than the current number, continue the loop, maybe the next number fit.
			continue
		}
		combination = append(combination, candidates[i]) // Add the current number to the combination.
		// repeat the same number in the combination, so we don't need to increase i. because we can use the same number in the next combination.
		backtrack(candidates, target-candidates[i], i, combination, result) // Recur with the next number.
		// no matter if we find a result item by backtrack, we will remove the last number from the combination so that we can scan the remain number in this loop.
		combination = combination[:len(combination)-1] // Backtrack by removing the last number.
	}
}

// The backtrack function is a recursive function that explores all possible combinations of numbers
// from the candidates list. It starts from the given index and tries to build combinations that sum up to the target value.
// The function uses a combination slice to keep track of the current combination being built.
// When a valid combination is found (i.e., the target becomes 0), it is added to the result slice.
// The function continues to explore other combinations by recursively calling itself with the updated target and combination.
// The backtrack function also handles the case where the target becomes negative by breaking out of the loop.
// The function uses a for loop to iterate through the candidates list, starting from the given index.
// It adds the current candidate to the combination and recursively calls itself with the updated target.
// After the recursive call, it removes the last added candidate from the combination to backtrack and explore other possibilities.
// The function continues this process until all possible combinations have been explored.
// The result slice is passed by reference to avoid copying it in each recursive call.
// The function returns the result slice containing all valid combinations that sum up to the target value.
// The time complexity of the backtrack function is O(2^n), where n is the number of candidates.
// This is because, in the worst case, the function explores all possible combinations of candidates.
// The space complexity is O(n), where n is the maximum depth of the recursion stack.
